
        <html>
			<head>
			     <title>CVE-2016-0799简单分析 - mrh</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/papers/13433">http://drops.wooyun.org/papers/13433</a></h1>
				
      <p>
        <h1>0x00 内容简介</h1>

<hr />

<p>最近openssl又除了一系列问题，具体可以看<a href="https://drownattack.com/#faq-practical">这里</a>。<a href="https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-0799">CVE-2016-0799</a>只是其中一个比较简单的漏洞。造成漏洞的原因主要有两个。</p>

<ul>
<li><code>doapr_outch</code>中有可能存在整数溢出导致申请内存大小为负数</li>
<li><code>doapr_outch</code>函数在申请内存失败时没有做异常处理</li>
</ul>

<!--more-->

<h1>0x01 源码分析</h1>

<p>首先，去<a href="githun.com">github</a>上找到了这一次漏洞修复的<a href="https://github.com/openssl/openssl/commit/9cb177301fdab492e4cfef376b28339afe3ef663">commit</a>，可以看到主要修改的是<code>doapr_outch</code>函数。</p>

<p><img src="http://static.wooyun.org//drops/20160304/2016030404535967355diff.jpg" alt="p1" /></p>

<p>有了一个大致的了解之后，将代码切换到bug修复之前的版本。函数源码如下：</p>

<pre><code>#!cpp
697 static void                                                     
698 doapr_outch(char **sbuffer,
699             char **buffer, size_t *currlen, size_t *maxlen, int c)
700 {
701     /* If we haven't at least one buffer, someone has doe a big booboo */
702     assert(*sbuffer != NULL || buffer != NULL);
703             if (*buffer == NULL) {
704     /* |currlen| must always be &lt;= |*maxlen| */
705     assert(*currlen &lt;= *maxlen);
706 
707     if (buffer &amp;&amp; *currlen == *maxlen) {
708         *maxlen += 1024;
709         if (*buffer == NULL) {   
710             *buffer = OPENSSL_malloc(*maxl
711                 /* Panic! Can't really do anything sensible. Just return */
712                 return; //这里没有做异常处理直接返回了
713             }           
714             if (*currlen &gt; 0) {
715                 assert(*sbuffer != NULL);
716                 memcpy(*buffer, *sbuffer, *currlen);
717             }           
718             *sbuffer = NULL;
719         } else {        
720             *buffer = OPENSSL_realloc(*buffer, *maxlen);
721             if (!*buffer) {
722                 /* Panic! Can't really do anything sensible. Just return */
723                 return; //这里没有做异常处理直接返回了
724             }           
725         }               
726     }                   
727 
728     if (*currlen &lt; *maxlen) {
729         if (*sbuffer)   
730             (*sbuffer)[(*currlen)++] = (char)c;
731         else            
732             (*buffer)[(*currlen)++] = (char)c;
733     }                   
734 
735     return;             
736 }
</code></pre>

<p>我是看完了一篇<a href="https://guidovranken.wordpress.com/2016/02/27/openssl-cve-2016-0799-heap-corruption-via-bio_printf/">国外的分析文章</a>之后了解了整个漏洞的流程，这里我就试图反向的思考一下这个漏洞。希望可以提高从代码补丁中寻找重现流程的能力。</p>

<h3>1.1 寻找内存改写的方式</h3>

<p>因为通过补丁已经知道是<code>doapr_outch</code>函数导致的堆腐败问题，所以<code>doapr_outch</code>一定存在改写数据的代码段。可以看到除了728-734行代码是对内存的改写外，没有其他地方操作内存的内容了。</p>

<pre><code>#!cpp
728     if (*currlen &lt; *maxlen) {
729         if (*sbuffer)   
730             (*sbuffer)[(*currlen)++] = (char)c; //这里
731         else            
732             (*buffer)[(*currlen)++] = (char)c; //这里
733     }                   
</code></pre>

<p>这里改写内存的方式可以用伪代码简单总结一下：</p>

<pre><code>#!c
base[offset]=c
</code></pre>

<p>所以想要向指定的内存写入数据的话需要控制<code>base</code>与<code>offset</code>两个参数。而写入的数据是<code>c</code>。如果控制了<code>base</code>与<code>offset</code>那么每次调用函数就可以改写一个字节。</p>

<p>如果是有经验的开发人员可以很容易看出外部在调用的时候一定是循环调用了<code>doapr_outch</code>，看一看函数调用处的代码。</p>

<pre><code>#!c
425 static void
426 fmtstr(char **sbuffer,
427        char **buffer,
428        size_t *currlen,
429        size_t *maxlen, const char *value, int flags, int min, int max)
430 {
431     int padlen, strln;
432     int cnt = 0;
433 
434     if (value == 0)
435         value = "&lt;NULL&gt;";
436     for (strln = 0; value[strln]; ++strln) ;
437     padlen = min - strln;
438     if (padlen &lt; 0)
439         padlen = 0;
440     if (flags &amp; DP_F_MINUS)
441         padlen = -padlen;
442 
443     while ((padlen &gt; 0) &amp;&amp; (cnt &lt; max)) {
444         doapr_outch(sbuffer, buffer, currlen, maxlen, ' ');
445         --padlen;
446         ++cnt;
447     }
448     while (*value &amp;&amp; (cnt &lt; max)) {
449         doapr_outch(sbuffer, buffer, currlen, maxlen, *value++); //这里！
450         ++cnt;
451     }
452     ...
453  }               
</code></pre>

<p>可以看到，确实是通过循环来改写内存的。</p>

<h3>1.2 副作用编程</h3>

<blockquote>
  <p>函数副作用会给程序设计带来不必要的麻烦，给程序带来十分难以查找的错误，并且降低程序的可读性。严格的函数式语言要求函数必须无副作用。</p>
</blockquote>

<p>副作用编程带来的不必要麻烦有一句更通俗的话可以来说明。<strong>开发一时爽，调试火葬场</strong>。这里再来看一下</p>

<p><code>doapr_outch</code>的函数声明</p>

<pre><code>#!c
static void doapr_outch(char **, char **, size_t *, size_t *, int);
</code></pre>

<p>从声明不难看出<code>sbuffer</code>，<code>buffer</code>，<code>currlen</code>，<code>maxlen</code>这几个参数在函数第n次运行时候如果被改变了，那么第n+1次运行的时候，这些参数将使用上次改变了的值。</p>

<p>再结合代码写入处内存改写的方式，就可以肯定<code>sbuffer</code>和<code>buffer</code>一定有一个或者全部被改写了，导致进入了意料之外的逻辑。</p>

<pre><code>#!c
728     if (*currlen &lt; *maxlen) {
729         if (*sbuffer)   
730             (*sbuffer)[(*currlen)++] = (char)c; //这里
731         else            
732             (*buffer)[(*currlen)++] = (char)c; //这里
733     }             
</code></pre>

<p>因为<code>Malloc</code>或者<code>Realloc</code>出来的地址一定不是可控的，而系统传进来的<code>sbuffer</code>也一定不可控，再结合上面的代码，如果<code>sbuffer</code>或者<code>buffer</code>指向<code>NULL</code>的话，基址就是固定的了。</p>

<p>718行的代码会将<code>sbuffer</code>设置为空指针。而<code>buffer</code>编程空指针只能是申请内存失败的时候。</p>

<p>在结合上728-733行代码，要做到这一步一定要满足的条件是<code>*sbuffer</code>与<code>*buffer</code>都指向<code>NULL</code>，导致代码进入改写<code>*buffer</code>为基址的内存块。其他任何情况都无法做到内存开始地址可控。</p>

<p>所以再分代码，<strong>看流程是否可能将<code>*sbuffer</code>与<code>*buffer</code>赋值为NULL</strong>。</p>

<h3>1.3 改写sbuffer与buffer</h3>

<pre><code>#!c
697 static void                                                     
698 doapr_outch(char **sbuffer,
699             char **buffer, size_t *currlen, size_t *maxlen, int c)
700 {
701     /* If we haven't at least one buffer, someone has doe a big booboo */
702     assert(*sbuffer != NULL || buffer != NULL);
703             if (*buffer == NULL) {
704     /* |currlen| must always be &lt;= |*maxlen| */
705     assert(*currlen &lt;= *maxlen);
706 
707     if (buffer &amp;&amp; *currlen == *maxlen) {
708         *maxlen += 1024;
709         if (*buffer == NULL) {   
710             *buffer = OPENSSL_malloc(*maxl
711                 /* Panic! Can't really do anything sensible. Just return */
712                 return; //这里没有做异常处理直接返回了
713             }           
714             if (*currlen &gt; 0) {
715                 assert(*sbuffer != NULL);
716                 memcpy(*buffer, *sbuffer, *currlen);
717             }           
718             *sbuffer = NULL;//这里！
        ...
728     if (*currlen &lt; *maxlen) {
729         if (*sbuffer)   
730             (*sbuffer)[(*currlen)++] = (char)c;
731         else            
732             (*buffer)[(*currlen)++] = (char)c;
733     }                   
734 
735     return;             
736 }
</code></pre>

<p>在循环调用<code>doapr_outch</code>之后，当<code>*currlen == *maxlen</code>成立的时候就会进入内存申请模块，因为<code>*buffer</code>还没有申请过所以进入上面一个分支，申请内存后将<code>*sbuffer</code>设为NULL。</p>

<p>还需要将<code>*buffer</code>设为NULL。</p>

<pre><code>#!c
707     if (buffer &amp;&amp; *currlen == *maxlen) {
708         *maxlen += 1024;
709         if (*buffer == NULL) {   
710             *buffer = OPENSSL_malloc(*maxl
711                 /* Panic! Can't really do anything sensible. Just return */
712                 return; //这里没有做异常处理直接返回了
713             }           
714             if (*currlen &gt; 0) {
715                 assert(*sbuffer != NULL);
716                 memcpy(*buffer, *sbuffer, *currlen);
717             }           
718             *sbuffer = NULL;
719         } else {        
720             *buffer = OPENSSL_realloc(*buffer, *maxlen);
721             if (!*buffer) {
722                 /* Panic! Can't really do anything sensible. Just return */
723                 return; //这里没有做异常处理直接返回了
724             }           
725         }               
726     }    
</code></pre>

<p>再一次<code>*currlen == *maxlen</code>之后，又会进入内存分配阶段，这次会进入<code>Realloc</code>的分支，那么只要<code>realloc</code>失败的话，<code>*buffer</code>就会被赋值为NULL。</p>

<p>最简单的情况就是堆上内存用完了，这个时候buffer就是NULL了，这个时候就可以根据currlen以及后续的c来改写目标地址的数据了。但是堆上内存用完，导致申请内存返回NULL，是一件不可控的事情。</p>

<p>那么除了这种情况，还有什么情况下，realloc会返回NULL呢。</p>

<pre><code>#!c
375    void *CRYPTO_realloc(void *str, int num, const char *file, int line)
376    {
377        void *ret = NULL;
378
379        if (str == NULL)
380            return CRYPTO_malloc(num, file, line);
381
382        if (num &lt;= 0)
383            return NULL;
</code></pre>

<p>可以注意到在708行，对*maxlen做了增加1024的操作，那么如果maxlen怎么1024之后超过int的范围，就会导致realloc传入的size是一个负数。这个时候buffer就会因为realloc的参数错误被设置为NULL。然后因为出错，函数退出。</p>

<h3>1.3 出错不处理</h3>

<pre><code>#!c
448     while (*value &amp;&amp; (cnt &lt; max)) {
449         doapr_outch(sbuffer, buffer, currlen, maxlen, *value++); //这里！
450         ++cnt;
451     }
</code></pre>

<p>从这里可以看到，<code>*buffer</code>被设置为NULL，返回出来了。但是外面的循环什么都没干，又继续执行了。</p>

<p>这个时候就可以做内存改写了。currlen与c都是与我们传递的字符串相关的，这个很好理解了。</p>

<h1>0x02 小结</h1>

<hr />

<ul>
<li>开发过程中出错一定要处理</li>
<li>数据类型不同，在隐形的转换时，一定要小心</li>
</ul>

<p>接下来要做的事情就是根据对漏洞的理解编写一个POC来调试。这样可以加深对漏洞的理解。在开发中也能更好的引以为戒。</p>

<h1>0x03 参考</h1>

<p>1.OpenSSL CVE-2016-0799: heap corruption via BIO_printf</p>

<p><a href="https://guidovranken.wordpress.com/2016/02/27/openssl-cve-2016-0799-heap-corruption-via-bio_printf/">https://guidovranken.wordpress.com/2016/02/27/openssl-cve-2016-0799-heap-corruption-via-bio_printf/</a></p>

<p><strong>PS：</strong></p>

<p>这是我的学习分享博客<a href="http://turingh.github.io/">http://turingh.github.io/</a></p>

<p>欢迎大家来探讨，不足之处还请指正。</p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          